Если бы вместо алгоритма Tree-Search использовался алгоритм Graph-Search, приведенный в листинге 3.6, то данное доказательство стало бы недействительным. Дело в том, что алгоритм Graph-Search способен отбросить оптимальный путь к повторяющемуся состоянию, если он не был сформирован в первую очередь, поэтому может возвращать неоптимальные решения (см. упр. 4.4). Существуют два способа устранения этого недостатка. Первое решение состоит в том, что алгоритм Graph-Search должен быть дополнен так, чтобы он отбрасывал наиболее дорогостоящий из любых двух найденных путей к одному и тому же узлу (см. обсуждение этой темы в разделе 3.5). Сопровождение необходимой для этого дополнительной информации связано с определенными трудностями, но гарантирует оптимальность. Второе решение состоит в обеспечении того, чтобы оптимальный путь к любому повторяющемуся состоянию всегда был первым из тех, по которым следует алгоритм, как в случае поиска по критерию стоимости.

Рис. 4.2. Этапы поиска А* пути в Бухарест. Узлы отмечены значениями f =g+h. Значения h представляют собой расстояния по прямой до Бухареста, приведенные в табл. 4.1